This invention gives a system and method for scheduling the priority among queries with different service level agreements and with imprecise query execution time.
Query scheduling is a fundamental problem in database systems. The focus of this invention is on cost-aware query scheduling algorithms, which are very important in traditional databases as well as platforms such as database-as-a-service (DaaS) in the cloud. In the cloud, because of service level agreements (SLAs), the scheduling decisions may have direct monetary consequences to service providers. However, existing cost-aware scheduling algorithms assumed that the exact query execution time of a query is known before the query is actually executed, which is an unrealistic assumption in most database systems. In such deployments, schedulers try to maximize performance with respect to service level agreements (SLAs) that may impose financial penalties for missed deadlines.
While there has been a great deal of work investigating different scheduling algorithms, there has been comparatively little work investigating what the scheduling algorithms can or should know about the queries to be scheduled. Clearly, the ideal would be to know the precise running time for every query in advance of its execution; in some sense this is “perfect” knowledge about the queries to be run and one cannot do better.
Previously, there were two approaches to the problem. One is to assume the exact query execution time is known beforehand. Such an assumption is rarely valid in real applications. The second approach is to use certain estimations on query execution time, such as the mean execution time or max execution time. Such estimations will mislead the scheduling decisions and therefore result in bad performances.
Conventional query scheduling to meet the requirements of SLAs has at least implicitly assumed that such information is available; unfortunately, this ideal is most likely not achievable in many real-world scenarios. The reason this is not achievable is simple: estimating the running time of queries is a notoriously difficult problem, as query running time is a complex function of the query itself (including any run-time parameters), the data over which it is run, and the environment in which it executes (including both the static hardware configuration and dynamic factors such as the contents of the buffer pool and the impact of concurrently running queries.) Despite a great deal of decade-old and recent effort, accurate prediction of query running times for dynamic, concurrent workloads remains largely elusive.